﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

public class Node
{
    public int val;
    public Node next;
    public Node random;

    public Node(int _val)
    {
        val = _val;
        next = null;
        random = null;
    }
}

public class Solution138
{
    //迭代
    public Node CopyRandomList2(Node head)
    {

        //使用map记录拷贝节点和旧节点的关系
      Dictionary<Node,Node> map = new Dictionary<Node,Node>();


        Node newHeaddummy = new Node(-1);
        Node newCur = newHeaddummy;

        Node cur = head;
        while (cur != null)
        {
            Node newNode = new Node(cur.val);
            newCur.next = newNode;

            map.Add( cur, newNode);  
            cur = cur.next;
            newCur = newCur.next;


        }

        cur = head;
        newCur = newHeaddummy.next;


        while (cur != null)
        {
            Node random = cur.random;//可能为空
            if(random!= null)
            {
                Console.WriteLine(random.val);
                Node newRandom = map[random];
                newCur.random = newRandom;
            }
            
          

            cur = cur.next;
            newCur = newCur.next;

        }

        return newHeaddummy.next;

    }
    //递归
    //使用map记录拷贝节点和旧节点的关系
    Dictionary<Node, Node> dict = new Dictionary<Node, Node>();
    public Node CopyRandomList(Node head)
    {

      if(head == null)
        {
            return head;
        }


     
        if (!dict.ContainsKey(head))
        {
            Node newNode = new Node(head.val);
            dict[head] = newNode;

            newNode.next = CopyRandomList(head.next);//取next对应的节点即可
            newNode.random = CopyRandomList(head.random);//取random对应的节点即可


        }

       
        return dict[head];

    }
}


class Program138
{

    static void Main138(string[] args)
    {
        Node head = new Node(7);
        Node tail = new Node(13);
        head.next = tail;
        tail.random = head;

        Solution138 solution = new Solution138();   
        solution.CopyRandomList(head);


    }
}